package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.book.BOfferS;
import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.knowledge.KStack;

import java.util.Stack;

@DRed
@KStack
@BOfferS(40)
public class LC85_MaximalRectangle {
    public static void main(String[] args) {
        String[] matrix = {"10100","10111","11111","10010"};
        int max = new Solution().maximalRectangle(matrix);
        System.out.println(max);
    }

    static class Solution {
        public int maximalRectangle(String[] matrix) {
            if(matrix.length == 0 || matrix[0].length() == 0) {
                return 0;
            }

            int[] heights = new int[matrix[0].length()];
            int maxArea = 0;
            for (String row : matrix) {
                for (int i = 0; i < row.length(); i++) {
                    if(row.charAt(i) == '0') {
                        heights[i] = 0;
                    } else {
                        heights[i]++;
                    }
                }
                maxArea = Math.max(maxArea, largestRectangleArea(heights));
            }
            return maxArea;
        }

        private int largestRectangleArea(int[] heights) {
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            int largestArea = 0;
            for (int i = 0; i < heights.length; i++) {
                while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                    int height = heights[stack.pop()];
                    int width = i - stack.peek() - 1;
                    largestArea = Math.max(largestArea, height * width);
                }
                stack.push(i);
            }
            while (stack.peek() != -1) {
                int height = heights[stack.pop()], width = heights.length - stack.peek() - 1;
                largestArea = Math.max(largestArea, height * width);
            }
            return largestArea;
        }
    }
}